【题解】 [SDOI2009]学校食堂 状压DP luoguP2157 | Qiuly's blog!

【题解】 [SDOI2009]学校食堂 状压DP luoguP2157

Posted on | In | Comments:

观察发现 $\texttt{B}​$ 及其的小，可以想到对于第 $i​$ 个人，状压自己以及自己后面 $7​$ 个人的打饭状态即可。

设 $dp_{i,j}$ 表示打饭到第 $i$ 个人，第 $i$ 个人以及其后面 $7$ 人的打饭状态为 $j$ 的时候的最短时间。转移的时候看在当前状态 $j$ 下有那些人没有打饭，然后给其打饭转移即可(显然还有忍耐度的限制)。

但是经过打饭操作我们无法得出这道菜的时间——因为我们不清楚上一个打饭的是谁。这个时候再记一维状态即可。

设 $dp_{i,j,k}$ 表示( $i,j$ 的意义与上面相同)，上一次打饭的人的编号就是 $i+k$ (注意 $k$ 的取值为 $-8$ 至 $7$ ，所以实际实现中我们需要将 $k$ 加上 $8$ 后再记入数组) 。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e3+2;
const int M=256;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int n,t[N],b[N],dp[N][M+2][16];
void cmin(int&x,int y) {x=min(x,y);}
void cmax(int&x,int y) {x=max(x,y);}
void solve() {
    IN(n);
    for(int i=1;i<=n;++i) IN(t[i]),IN(b[i]);
    memset(dp,127,sizeof(dp));
    int inf=dp[0][0][0];
    dp[1][0][7]=0;
    for(int i=1;i<=n;++i) for(int j=0;j<M;++j)
        for(int k=-8;k<=7;++k) if(dp[i][j][k+8]!=inf) {
            if(j&1) cmin(dp[i+1][j>>1][k+7],dp[i][j][k+8]);
            else {
                int max_pos=inf;
                for(int h=0;h<=7;++h) if(!((j>>h)&1)) {
                    if(i+h>max_pos) break;
                    cmin(max_pos,i+h+b[i+h]);
                    cmin(dp[i][j|(1<<h)][h+8],dp[i][j][k+8]+(i+k?t[i+h]^t[i+k]:0));
                }
            }
        }
    int ans=inf;
    for(int i=0;i<=8;++i) cmin(ans,dp[n+1][0][i]);
    printf("%d\n",ans);
    return;
}

int main() {
    int T;IN(T);
    while(T--) solve();
    return 0;
}

本文标题:【题解】 [SDOI2009]学校食堂 状压DP luoguP2157

文章作者:Qiuly

发布时间:2019年05月17日 - 00:00

最后更新:2019年05月17日 - 10:03

原始链接:http://qiulyblog.github.io/2019/05/17/[题解]luoguP2157/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。